package Graph_10;

/*
 * @Author 罗
 * @date 2020/3/27 - 6:39 下午
 *
 */

import Queue_02.Queue;

import java.util.*;

public class Graph {
    /*
     * 用于存放边
     * 二维矩阵的下标代表图的节点（正向）
     * 一维矩阵的下标代表图的节点（逆向）
     * */
    private int[][] edges;
    /*
     * 用于存储节点的名字
     * 用于映射边和节点的关系
     * */
    private ArrayList<String> vertexList;
    /*
     * 边的数量
     * */
    private int numberOfEdges;
    /*
     * 反向 可以通过节点名字找到对应下标，和vertexList作用刚好相反
     */
    private Map<String, Integer> mapEdgesAndVertexes;

    public void bfsEnhance() {

        boolean[] hasBeenVisited = new boolean[vertexList.size()];
        /*
         * 简单情况下并不需要遍历所有顶点，但是在服务器环境中，多个图并存
         * 图可能是多个程序员创建的，所以无法用单一顶点广度优先遍历出所有节点
         */
        for (int i = 0; i < vertexList.size(); i++) {
            if (!hasBeenVisited[i]) {
                bfs1(i, hasBeenVisited);
            }
        }
    }

    /**
     * 比较好的bfs 广度优先遍历
     *
     * @param vertex
     * @param hasBeenVisited
     */
    private void bfs1(int vertex, boolean[] hasBeenVisited) {
        /*
         * 为每个图创建一个队列
         * 用于记录节点的访问顺序
         * */
        Queue<Integer> queue = new Queue<Integer>(Integer.class, 10);
        /*
         * 表示头节点的对应下标
         * */
        int u;
        /*
         * 记录领接节点
         * */
        int w;
        /*
         * 访问第一个传入该图的顶点，并输出
         * */
        System.out.print(vertexList.get(vertex) + "\t->\t");
        /*
         * 将该顶点标记为已访问
         * */
        hasBeenVisited[vertex] = true;
        /*
         * 将该顶点添加到队列
         * */
        queue.addQueue(vertex);
        /*
         * 只要队列不为null，就一直广度优先遍历
         * */
        while (!queue.isEmpty()) {
            /*
             * 获取队列头节点的下标
             * */
            u = queue.getHead();
            /*
             * 获取第一个与头节点相邻的节点
             * */
            w = getFirstValidNeighbor(u);

            while (w != -1) {
                /*
                 * 进入while循环，说明有和头节点相邻的节点
                 * */
                if (!hasBeenVisited[w]) {
                    /*
                     * 这个相邻的节点还没有被访问过
                     * 先访问该节点
                     * */
                    System.out.print(vertexList.get(w) + "\t->\t");
                    /*
                     * 设置该节点为已经访问
                     * */
                    hasBeenVisited[w] = true;
                    /*
                     * 把该节点添加到队列
                     * */
                    queue.addQueue(w);
                }
                /*
                 * 获取头节点的下一个相邻节点，相对与w的下一个节点
                 * 这里体现广度优先
                 * */
                w = getNextVertex(vertex, w);
            }
        }
    }

    /**
     * 图的广度优先搜索
     */
    public void broadFirstSearch() {
        boolean[] hasBeenVisited = new boolean[vertexList.size()];
        /*
         * 队列：记录节点访问顺序
         * 本队列是自己写的
         * LinkedList也可以当作队列用，
         * addLast();
         * removeFirst();
         * */
        Queue<Integer> queue = new Queue<>(Integer.class, 10);

        for (int i = 0; i < vertexList.size(); i++) {
            if (!hasBeenVisited[i]) {
                bfs(hasBeenVisited, i, queue);
            }
        }
    }

    /**
     * 按照步骤，循规蹈矩
     * <p>
     * 广度优先遍历的算法步骤
     * 1.访问初始节点v，并且标记节点v为已访问
     * 2.节点v加入队列
     * 3.当队列非null时，继续执行，否则对v的算法结束，并将v的下一个节点设置为v，从第一步继续执行
     * 4.出队列，取得队列头节点u
     * 5.查找节点u的第一个相邻节点w
     * 6.若节点u的相邻节点w不存在，则跳转到步骤3，否则继续执行下面的三个步骤
     * 6.1 若节点w尚未被访问，则访问节点w并标记为已经访问
     * 6.2 节点w加入队列
     * 6.3 查找节点u的继w邻节点之后的下一个邻节点w，转到步骤6
     * A入，A出bc入，b出de进，c出，d出，e出
     *
     * @param hasBeenVisited
     * @param vertex
     * @param queue
     */
    private void bfs(boolean[] hasBeenVisited, int vertex, Queue<Integer> queue) {

        System.out.print(vertexList.get(vertex) + "-->");

        hasBeenVisited[vertex] = true;
        /*
         * 1.访问初始节点v，并且标记节点v为已访问
         * 2.节点v加入队列
         * */
        queue.addQueue(vertex);
        int neighbor = step3(queue);
        if (neighbor == -1) {
            return;
        }
        step6(hasBeenVisited, neighbor, queue, vertex);
    }

    /**
     * 3.当队列非null时，继续执行，否则对v的算法结束，并将v的下一个节点设置为v，从第一步继续执行
     * 4.出队列，取得队列头节点u
     * 5.查找节点u的第一个相邻节点w
     * 6.若节点u的相邻节点w不存在，则跳转到步骤3，否则继续执行下面的三个步骤
     *
     * @param queue
     * @return
     */
    private int step3(Queue<Integer> queue) {
        if (queue.isEmpty()) {
            return -1;
        }
        /*
         * 4.出队列，取得队列头节点u
         *
         * */
        int queueHead = queue.getHead();
        /*
         * 5.查找节点u的第一个相邻节点w
         * */
        int neighbor = getFirstValidNeighbor(queueHead);
        /*
         * 6.若节点u的相邻节点w不存在，则跳转到步骤3，否则继续执行下面的三个步骤
         * */
        if (neighbor == -1) {
            step3(queue);
        }
        return neighbor;
    }

    /**
     * 6.1 若节点w尚未被访问，则访问节点w并标记为已经访问
     * 6.2 节点w加入队列
     * 6.3 查找节点u的继w邻节点之后的下一个邻节点w，转到步骤6
     *
     * @param hasBeenVisited
     * @param neighbor
     * @param queue
     * @param vertex
     */
    private void step6(boolean[] hasBeenVisited, int neighbor, Queue<Integer> queue, int vertex) {
        if (!hasBeenVisited[neighbor]) {
            /*
             * 6.1 若节点w尚未被访问，则访问节点w并标记为已经访问
             * */
            hasBeenVisited[neighbor] = true;
            System.out.print(vertexList.get(neighbor) + "-->");
            /*
             * 6.2 节点w加入队列
             * */
            queue.addQueue(neighbor);
            /*
             * 6.3 查找节点u的继w邻节点之后的下一个邻节点w，转到步骤6
             * */
            int nextNeighbor = getNextVertex(vertex, neighbor);
            if (nextNeighbor != -1) {
                step6(hasBeenVisited, nextNeighbor, queue, vertex);
            }
        }
    }

    /**
     * 图的深度优先遍历
     */
    public void depthFirstSearch() {
        /*
         * 用于标记该节点是否被访问过
         * */
        boolean[] hasBeenVisited = new boolean[vertexList.size()];
        /*
         * 继续深度优先遍历其他顶点
         * vertex++  切换到下一个顶点
         * */
        for (int vertex = 0; vertex < vertexList.size(); vertex++) {
            /*
             * 如果没有被访问过，才访问
             * 提升效率
             * 因为System.out.print(vertexList.get(vertex) + "\t->\t");
             *       在dfs() 的 第一行，所以进去就会打印，即使该节点已经被遍历过了
             * 所以这里的if防止已经打印过的节点再打印一次
             * */
            if (!hasBeenVisited[vertex]) {
                dfs(hasBeenVisited, vertex);
                System.out.println();
            }
        }

    }

    /**
     * 图的深度优先遍历
     */
    private void dfs(boolean[] hasBeenVisited, int vertex) {
        /*
         * (1)输出该节点的信息
         * */
        System.out.print(vertexList.get(vertex) + "\t->\t");
        /*
         * (2)将该节点vertex设置为已经访问
         * */
        hasBeenVisited[vertex] = true;
        /*
         * (3)查找节点v的第一个相邻节点validSubscript
         * 获取第一个有效相邻顶点的下标
         * */
        int validSubscript = getFirstValidNeighbor(vertex);
        /*
         * (3.1)若validSubscript节点存在，则继续执行步骤(4)
         * */
        while (validSubscript != -1) {
            /*
             * (4)这个顶点有有效的相邻节点
             * */
            if (!hasBeenVisited[validSubscript]) {
                /*
                 * (4.1)这个有效的相邻节点还没有被访问过
                 * 开始递归
                 * */
                dfs(hasBeenVisited, validSubscript);
            }
            /*
             * (4.2)有效的相邻节点已经被访问过
             * 不进行递归，并寻找下一个相邻的节点
             * */
            validSubscript = getNextVertex(vertex, validSubscript);
        }
        /*
         *(3.2)validSubscript节点不存在，返回执行步骤(1)
         * 通过depthFirstTraversal()的for循环执行
         * */

    }

    /**
     * 根据前一个相邻节点的下标(x,y1)来获取下一个相邻节点的下标(y2)
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getNextVertex(int v1, int v2) {
        /*
         * +1 的作用
         * 从当前节点的下一个开始判断，无需再把本节点判断一次
         * 跳过自身的判断
         * */
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (edges[v1][i] != 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 获得第一个有效相邻节点的下标
     *
     * @param index
     * @return 如果存在，就返回相邻节点对应的下标，如果不存在就返回-1
     */
    public int getFirstValidNeighbor(int index) {

        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] != 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 添加边，无向图
     *
     * @param vertex1
     * @param vertex2
     * @param weight
     */
    public void addEdge(String vertex1, String vertex2, int weight) {
        Integer vertexSubscript1 = this.mapEdgesAndVertexes.get(vertex1);
        Integer vertexSubscript2 = this.mapEdgesAndVertexes.get(vertex2);
        if (vertexSubscript1 != null && vertexSubscript2 != null) {
            /*
             * 正向添加边
             * */
            this.edges[vertexSubscript1][vertexSubscript2] = weight;
            /*
             * 逆向添加边
             * */
            this.edges[vertexSubscript2][vertexSubscript1] = weight;
        } else {
            System.out.println("节点不存在，添加边 失败");
            return;
        }

    }


    /**
     * 添加节点
     *
     * @param vertex
     */
    public void addVertex(String vertex) {

        this.vertexList.add(vertex);
        this.mapEdgesAndVertexes.put(vertex, this.numberOfEdges);
        this.numberOfEdges++;
    }

    public Graph(int numberOfVertex) {
        this.vertexList = new ArrayList<String>(numberOfVertex);
        this.edges = new int[numberOfVertex][numberOfVertex];
        /*
         * 只传入有几个节点，并没有说有多少条边
         * */
        this.numberOfEdges = 0;
        this.mapEdgesAndVertexes = new HashMap<>();
    }

    public void show() {

        System.out.print("\n\t");
        for (String s : vertexList) {
            System.out.print(s + "\t");
        }
        System.out.println();
        for (int i = 0; i < vertexList.size(); i++) {
            System.out.print(vertexList.get(i) + "\t");
            for (int i1 = 0; i1 < vertexList.size(); i1++) {
                System.out.print(edges[i][i1]+"\t");
            }
            System.out.println();
        }

    }
}
